package algorithm.leetcode.I401to600;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 用上下左右找短板的方法是不对的,因为水可能从连通的地方流走
 * 简言之,背答案即可
 */

public class Q407 {

    public int trapRainWater(int[][] heightMap) {
        int row = heightMap.length, col = heightMap[0].length;
        int maxHeight = 0, volume = 0;
        // 存储的是长度为3的数组,前两位是数字的坐标,最后一位是柱子的高度,建立最小堆
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        boolean[][] isSearched = new boolean[row][col];
        // heightMap边框入队
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (i == 0 || i == row-1 || j == 0 || j == col-1) {
                    pq.add(new int[]{i, j, heightMap[i][j]});
                    isSearched[i][j] = true;
                }
            }
        }

        // 开始BFS,出队一个位置上的柱子,如果这个柱子在边框内,容积加上maxHeight减去这个位置柱子的高度的差(要大于0),更新maxHeight,入队这个位置的上下左右位置
        // BFS的基本套路是while循环中,出队一个元素,对该元素进行操作,然后入队和这个元素相连接的元素
        while (!pq.isEmpty()) {
            // 出队一个位置上的柱子
            int[] poll = pq.poll();
            int temp = maxHeight - heightMap[poll[0]][poll[1]];
            // 如果这个柱子在边框内,容积加上maxHeight减去这个位置柱子的高度的差(要大于0)
            if (poll[0] > 0 && poll[0] < row-1 && poll[1] > 0 && poll[1] < col-1 && temp > 0) volume += temp;
            // 更新maxHeight
            maxHeight = Math.max(maxHeight, poll[2]);

            // 入队这个位置的上下左右位置
            for (int i = -1; i <= 1; i++) {
                if (i != 0 && poll[0]+i >= 0 && poll[0]+i <= row-1 && !isSearched[poll[0]+i][poll[1]]) {
                    pq.add(new int[]{poll[0]+i, poll[1], heightMap[poll[0]+i][poll[1]]});
                    isSearched[poll[0]+i][poll[1]] = true;
                }
                if (i != 0 && poll[1]+i >= 0 && poll[1]+i <= col-1 && !isSearched[poll[0]][poll[1]+i]) {
                    pq.add(new int[]{poll[0], poll[1]+i, heightMap[poll[0]][poll[1]+i]});
                    isSearched[poll[0]][poll[1]+i] = true;
                }
            }
        }
        return volume;
    }

}
